/*
 * @Author: dengzhijun mento@dengzhijun
 * @Date: 2025-09-30
 * @LastEditors: dengzhijun mento@dengzhijun
 * @LastEditTime: 2025-09-30
 * @FilePath: /MenTo/EasyAOI/Common/Log/lock_free_queue.h
 * @Description: 基于循环数组的无锁队列实现
 * Copyright (c) 2024 by Mento/dengzhijun, All Rights Reserved.
 */

#ifndef TOOLS_LOCK_FREE_QUEUE_H_
#define TOOLS_LOCK_FREE_QUEUE_H_

#include <vector>
#include <atomic>
#include <stdexcept>
#include <chrono>
#include <thread>
#include <type_traits>

namespace Tool
{

template <class T>
class LockFreeQueue
{
public:
    //在构造函数的初始化列表中，成员变量的初始化顺序不是按照列表中的顺序，而是按照它们在类中声明的顺序。
    explicit LockFreeQueue(size_t maxSize = 1000)
         : m_maxSize(nextPowerOfTwo(maxSize)),
//        : m_maxSize(maxSize),
        m_buffer(m_maxSize),
        m_head(0),
        m_tail(0),
        m_running(true)
    {
        if (m_buffer.empty())
        {
            throw std::runtime_error("Failed to allocate memory for queue");
        }
    }

    LockFreeQueue(const LockFreeQueue&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue&) = delete;

    ~LockFreeQueue()
    {
        Stop();
    }

    LockFreeQueue(LockFreeQueue&& other) noexcept
        : m_maxSize(other.m_maxSize),
        m_buffer(std::move(other.m_buffer)),
        m_head(other.m_head.load()),
        m_tail(other.m_tail.load()),
        m_running(other.m_running.load())
    {
        other.m_head.store(0);
        other.m_tail.store(0);
        other.m_running.store(false);
    }

    LockFreeQueue& operator=(LockFreeQueue&& other) noexcept(
        std::is_nothrow_move_constructible<LockFreeQueue>::value &&
            std::is_nothrow_move_assignable<LockFreeQueue>::value
        )
    {
        if (this != &other)
        {
            m_maxSize = other.m_maxSize;
            m_buffer = std::move(other.m_buffer);
            m_head.store(other.m_head.load());
            m_tail.store(other.m_tail.load());
            m_running.store(other.m_running.load());

            other.m_head.store(0);
            other.m_tail.store(0);
            other.m_running.store(false);
        }
        return *this;
    }

    void Clear()
    {
        size_t currentHead = m_head.load(std::memory_order_relaxed);
        m_head.store(currentHead, std::memory_order_release);
        m_tail.store(currentHead, std::memory_order_release);
    }

    bool IsEmpty() const
    {
        size_t head = m_head.load(std::memory_order_acquire);
        size_t tail = m_tail.load(std::memory_order_acquire);
        return head == tail;
    }

    bool IsFull() const
    {
        size_t head = m_head.load(std::memory_order_acquire);
        size_t tail = m_tail.load(std::memory_order_acquire);
        return (tail + 1) % m_maxSize == head;
    }

    bool Push(const T& item)
    {
        if (!m_running.load(std::memory_order_acquire))
        {
            return false;
        }

        size_t currentTail;
        size_t nextTail;

        while (true)
        {
            currentTail = m_tail.load(std::memory_order_acquire);
            nextTail = (currentTail + 1) % m_maxSize;

            // 检查队列是否已满
            if (nextTail == m_head.load(std::memory_order_acquire))
            {
                return false;
            }

            /*
            * 尝试更新tail指针,
            * compare_exchange_weak 可能虚假失败（即使值相等也可能失败），所以通常用在循环中。
            * compare_exchange_strong 不会虚假失败，但可能性能略差。
            */
            if (m_tail.compare_exchange_weak(currentTail, nextTail, std::memory_order_release, std::memory_order_relaxed))
            {
                break;
            }

            // CAS失败，短暂休息后重试 让出CPU，让其他线程有机会运行
            std::this_thread::yield();
        }

        // 存储数据
        m_buffer[currentTail] = item;
        return true;
    }

    bool Push(T&& item)
    {
        if (!m_running.load(std::memory_order_acquire))
        {
            return false;
        }

        size_t currentTail;
        size_t nextTail;

        while (true)
        {
            currentTail = m_tail.load(std::memory_order_acquire);
            nextTail = (currentTail + 1) % m_maxSize;

            if (nextTail == m_head.load(std::memory_order_acquire))
            {
                return false;
            }

            if (m_tail.compare_exchange_weak(currentTail,nextTail,std::memory_order_release,std::memory_order_relaxed))
            {
                break;
            }
            std::this_thread::yield();
        }

        m_buffer[currentTail] = std::move(item);
        return true;
    }

    bool Pop(T& item)
    {
        if (!m_running.load(std::memory_order_acquire))
        {
            return false;
        }

        size_t currentHead;
        size_t nextHead;

        while (true)
        {
            currentHead = m_head.load(std::memory_order_acquire);

            if (currentHead == m_tail.load(std::memory_order_acquire))
            {
                return false;
            }

            nextHead = (currentHead + 1) % m_maxSize;
            if (m_head.compare_exchange_weak(currentHead,nextHead,std::memory_order_release,std::memory_order_relaxed))
            {
                break;
            }

            std::this_thread::yield();
        }

        item = std::move(m_buffer[currentHead]);
        return true;
    }

    bool TryPop(T& item, std::chrono::milliseconds timeout)
    {
        auto start = std::chrono::steady_clock::now();
        while (true)
        {
            if (!m_running.load(std::memory_order_acquire))
            {
                return false;
            }

            size_t currentHead = m_head.load(std::memory_order_acquire);
            if (currentHead != m_tail.load(std::memory_order_acquire))
            {
                size_t nextHead = (currentHead + 1) % m_maxSize;
                if (m_head.compare_exchange_weak(currentHead,nextHead,std::memory_order_release,std::memory_order_relaxed))
                {
                    item = std::move(m_buffer[currentHead]);
                    return true;
                }
            }

            auto now = std::chrono::steady_clock::now();
            if (now - start >= timeout)
            {
                return false;
            }
            std::this_thread::yield();
        }
    }

    void Stop()
    {
        m_running.store(false, std::memory_order_release);
    }

    bool Running() const
    {
        return m_running.load(std::memory_order_acquire);
    }

    size_t Size() const
    {
        size_t head = m_head.load(std::memory_order_acquire);
        size_t tail = m_tail.load(std::memory_order_acquire);

        if (tail >= head)
            return tail - head;
        return (m_maxSize - head) + tail;
    }

private:
    // 计算大于等于n的最小2的幂，优化取模运算
    size_t nextPowerOfTwo(size_t n)
    {
        if (n == 0)
        {
            return 1;
        }
        if ((n & (n - 1)) == 0)
        {
            return n;
        }

        size_t result = 1;
        while (result < n)
        {
            result <<= 1;
        }
        return result;
    }

    alignas(64) size_t m_maxSize;
    alignas(64) std::vector<T> m_buffer;
    alignas(64) std::atomic<size_t> m_head;  // 下一个要出队的元素位置
    alignas(64) std::atomic<size_t> m_tail;  // 下一个要入队的位置
    alignas(64) std::atomic<bool> m_running;
};

}
#endif
